import java.util.Arrays;

/**
 * 双边循环快排（不完全等价于 hoare 霍尔分区方案）
 */
@SuppressWarnings("all")
public class QuickSort2 {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        System.out.println(Arrays.toString(a));
        quick(a, 0, a.length - 1);
    }

    /**
     * 算法描述：
     * <p>
     * 1. 选择最左元素作为基准点元素
     * <p>
     * 2. j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交
     * <p>
     * 3. 最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置
     * <p>
     * 要点：
     * <p>
     * 1. 基准点在左边，并且要先 j 后 i
     * <p>
     * 2. while( **i** **< j** && a[j] > pv ) j--
     * <p>
     * 3. while ( **i** **< j** && a[i] **<=** pv ) i++
     */
    private static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h);
        quick(a, l, p - 1);
        quick(a, p + 1, h);
    }

    private static int partition(int[] a, int l, int h) {
        int pv = a[l];
        int i = l;
        int j = h;
        while (i < j) {
            // j 从右找小的
            while (i < j && a[j] > pv) {
                j--;
            }
            // i 从左找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            swap(a, i, j);
        }
        swap(a, l, j);
        System.out.println(Arrays.toString(a) + " j=" + j);
        return j;
    }


    public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
